package arithmetic.demo22;


import java.util.PriorityQueue;

/**
 * 贪心_买卖股票的最佳时机(2)
 */

class Solution {
    public int maxProfit(int[] prices) {
        // 使用双指针
        int begin = 0, ret = 0;
        int n = prices.length;
        for(int i =0; i< n - 1 ; i++) {
            if(prices[i] >= prices[i + 1]) {
                // 加入结果
                ret += prices[i] - prices[begin];
                begin = i + 1;
            }  

        }

        // 最后考虑最终结果加入结果
        ret += prices[n - 1] - prices[begin];


        return ret;
    }
}

/**
 * 题目： 贪心_买卖股票的最佳时机（2）_分解思维
 *
 */

class Solution1 {
    public int maxProfit(int[] prices) {
        // 使用双指针
        int  ret = 0;
        int n = prices.length;
        for(int i =0; i< n - 1 ; i++) {
            if(prices[i] < prices[i + 1]) {
                // 分解成一段一段
                ret +=  (prices[i + 1] - prices[i]);
            }

        }


        return ret;
    }
}


/**
 * 题目： 简单多状态 dp问题_按摩师
 */


class Solution2 {
    public int massage(int[] nums) {


        int n = nums.length;

        // 数组为 空的情况处理一下
        if(n == 0) return 0 ;
        // 创建两个dp 表
        int[] fp = new int[n];
        int[] gp = new int[n];

        // 初始化
        fp[0] = nums[0];

        // 进行状态转移
        for(int i = 1 ; i < n; i++) {
            // 当前位置不选
            gp[i] = Math.max(gp[i - 1], fp[i - 1]);

            // 当前位置需要选
            fp[i] = gp[i-1] + nums[i];
        }

        return Math.max(gp[n - 1], fp[n - 1]);
    }
}


/**
 * 题目： 简单多状态 dp问题_打家劫舍（1）
 */

class Solution3 {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        int[] fp = new int[n], gp = new int[n];

        fp[0] = nums[0];
        for(int i = 1; i < n ; i++) {
            // 需要选上的
            fp[i] = gp[i-1] + nums[i];

            // 不需要选上的
            gp[i] = Math.max(fp[i-1], gp[i-1]);
        }

        return Math.max(fp[n-1], gp[n-1]);
    }
}


/**
 * 题目： 简单多状态 dp 问题_打家劫舍(2)
 */


class Solution4 {

    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        // 第一个位置不偷
        int no = rob1(nums, 1, n - 1) ,yes = rob1(nums, 2, n - 2)  + nums[0] ;
        return Math.max(no , yes);
    }

    public int rob1(int[] nums, int begin , int end) {
        // 考虑没有元素的情况
        if(begin > end) return 0;
        int[] fp = new int[end + 1], gp = new int[end + 1];

        // 初始化
        fp[begin] = nums[begin];
        for(int i = begin + 1; i <= end ; i++) {
            // 需要选上的
            fp[i] = gp[i-1] + nums[i];

            // 不需要选上的
            gp[i] = Math.max(fp[i-1], gp[i-1]);
        }

        return Math.max(fp[end], gp[end]);
    }
}


/**
 * 贪心_K次取反后最大化的数组和
 */


class Solution5 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length;
        // 建立小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b)->{
            return a - b;
        });

        int sum = 0;
        // 加入堆并且计算总和
        for(int i = 0; i < n ; i++) {
            int num = nums[i];
            queue.add(num);
            sum += num;
        }

        // 进行k 次取反
        while(k-- > 0) {
            int num = queue.poll();
            sum -= (2 * num);
            queue.add(-num);
        }

        return sum;
    }
}


/**
 * 贪心_按身高排序
 */

class Solution6 {
    public String[] sortPeople(String[] names, int[] heights) {
        bubbleSort(names, heights);
        return names;
    }

    public void bubbleSort(String[] names, int[] heights) {
        int n = 0 ;
        for(int i =0; i < heights.length - 1 ; i++) {
            for(int j = 1; j <  heights.length  -  i ; j++) {
                if(heights[j-1] < heights[j]) {
                    //    交换身高
                    int t = heights[j - 1];
                    heights[j - 1] =  heights[j];
                    heights[j] = t;

                    //    交换名字
                    String tmp =  names[j-1];
                    names[j-1] = names[j];
                    names[j] = tmp;

                }
            }
        }
    }
}